/*
 * @lc app=leetcode.cn id=98 lang=cpp
 *
 * [98] 验证二叉搜索树
 *
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 *
 * algorithms
 * Medium (37.51%)
 * Likes:    2263
 * Dislikes: 0
 * Total Accepted:    836.6K
 * Total Submissions: 2.2M
 * Testcase Example:  '[2,1,3]'
 *
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 
 * 有效 二叉搜索树定义如下：
 * 
 * 
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [2,1,3]
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数目范围在[1, 10^4] 内
 * -2^31 <= Node.val <= 2^31 - 1
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了
    //我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点

    //preVal 只能是个引用, 并且需要先遍历到最左的叶子节点
    //然后记录当前节点的 preval, 再向上比较
    bool isValidBST(TreeNode* root, int64_t& preVal) {
        if (root == nullptr)
            return true;

        bool isLeftBST = isValidBST(root->left, preVal);    //左

        if (root->val <= preVal) //中
            return false;
        preVal = root->val;     //为了先进入最左边的叶子节点
                                //若 PreVal 直接传入 root->val, 直接就return false 了

        bool isRightBST = isValidBST(root->right, preVal);  //右

        return isLeftBST && isRightBST;
    }

    //为什么 leetcode 的编译器不行？
    //leetcode 每次提交共享一个程序实例
    //https://blog.csdn.net/m0_65280246/article/details/126532235
    bool isValidBST(TreeNode* root) {
        //static long long preVal = LONG_MIN;   //不能 static ↑

        //中序遍历, 判断是否为有序数列
        int64_t preVal = LONG_MIN;
        return isValidBST(root, preVal);
    }
};
// @lc code=end

